from collections import defaultdict
from typing import List

from sortedcontainers import SortedList


class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.prices = {}
        self.movies = defaultdict(SortedList)
        self.renting = SortedList()

        for shop, movie, price in entries:
            self.prices[(shop, movie)] = price
            self.movies[movie].add([price, shop])

    def search(self, movie: int) -> List[int]:
        num = min(len(self.movies[movie]), 5)
        return [shop for price, shop in self.movies[movie][:num]]

    def rent(self, shop: int, movie: int) -> None:
        price = self.prices[(shop, movie)]
        self.movies[movie].remove([price, shop])
        self.renting.add([price, shop, movie])

    def drop(self, shop: int, movie: int) -> None:
        price = self.prices[(shop, movie)]
        self.movies[movie].add([price, shop])
        self.renting.remove([price, shop, movie])

    def report(self) -> List[List[int]]:
        num = min(len(self.renting), 5)
        return [[shop, movie] for price, shop, movie in self.renting[:num]]


if __name__ == "__main__":
    obj = MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]])
    print(obj.search(1))  # [1,0,2]
    obj.rent(0, 1)
    obj.rent(1, 2)
    print(obj.report())  # [[0, 1], [1, 2]]
    obj.drop(1, 2)
    print(obj.search(2))  # [0, 1]
    print()
